动态规划 - 子序列问题

之前说过，遇到求极值的问题我们首先可以考虑是否可以使用动态规划来解。

例如求最长子序列的系列问题。

首先最重要的一步是审题。注意最长子序列与最长子数组之间的区分，最长子数组要求连成的序列是连续的，而子序列是可以跳过子数组中某些元素的。

像这类问题，通常是设 dp[i] 为以 nums[i] 结尾的子序列的最值的求值结果。而既然是求子数组，那么通常 dp 数组就仅与 dp[i-1] 相关。若是求子序列，则 dp[i] 的结果可能需要遍历从 0 到 i 中的 dp 数组 ，取出其中的最大值来求解。

参考题型：

1. [300] 最长递增子序列
2. [674] 最长连续递增序列
3. [718] 最长重复子数组
4. [1143] 最长公共子序列
5. [647] 回文子串
6. [516] 最长回文子序列
7. [53] 最大子序和
8. [583] 两个字符串的删除操作
9. [72] 编辑距离